#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int val = 0, ListNode *nt = NULL): val(val), next(nt) {}
};

// 双指针判断链表是否存在环
bool hasCycle(ListNode *head) {
    ListNode *fast = head, *slow = head;

    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
            return true;
    }
    return false;
}

// 双指针求环的起始点
ListNode *cycleStart(ListNode *head) {
    ListNode *fast = head, *slow = head;

    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
            break;
    }
    // 链表为空/只有一个孤单节点，一定没有环
    if (fast == NULL || fast->next == NULL)
        return NULL;
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

// 双指针求链表中点
ListNode *midListNode(ListNode *head) {
    ListNode *fast = head, *slow = head;
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

// 删除链表倒数第n个节点
ListNode *removeTheNthFromEnd(ListNode *head, int n) {
    ListNode *fast = head, *slow = head;
    while (n--) 
        fast = fast->next;
    if (fast == NULL)
        // 此时删除节点为head
        return head->next;
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    return head;
}